package chapter01_stackandqueue;

import java.util.LinkedList;

/**
 * 描述：
 *
 * @author hl
 * @date 2021/1/21 9:42
 */
public class GetNum {
    public int getNum(int[] arr, int num){
        int i = 0, j = 0, res = 0, len = arr.length;
        LinkedList<Integer> qmax = new LinkedList<>();
        LinkedList<Integer> qmin = new LinkedList<>();
        while(i < len){
            while(j < len) {
                while (!qmax.isEmpty() && qmax.peekLast() <= arr[j]) {
                    qmax.pollLast();
                }
                qmax.addLast(j);
                while (!qmin.isEmpty() && qmin.peekLast() >= arr[j]) {
                    qmin.pollLast();
                }
                qmin.addLast(j);
                if (arr[qmax.peekFirst()] - arr[qmin.peekFirst()] > num) {
                    //如果条件成立，说明以i开头的子数组小于num的最大右边界为j-1
                    break;
                }
            }
            res += j - i;
            //i右移时更新窗口最大值
            if(qmax.peekFirst() == i){
                qmax.pollFirst();
            }
            if (qmin.peekFirst() == i) {
                qmin.pollLast();
            }
            i++;
        }
        return res;
    }
}
